package trees;

import java.util.*;

import lib.*;

/**
 * 
 * @author Reid Hironaga
 *
 * @param <NodeType>
 */
public class QuadTree<NodeType extends Comparable<NodeType>> implements Tree<NodeType>{

	/** 
	 * Initializes a new QuadTree covering the entire range of allowable 
	 * double values
	 */
	public QuadTree() {
		this(new RectangleArea(new CartesianPoint(-Double.MAX_VALUE, -Double.MAX_VALUE),
				new CartesianPoint(Double.MAX_VALUE, Double.MAX_VALUE)));
	}

	/**
	 * Initializes a new QuadTree restricted to the input area rectangle
	 */
	public QuadTree(RectangleArea area) {
		size = 0;
		coverage = area;
		root = new QuadTreeNode(CartesianPoint.midpoint(area.getLowLeft(), area.getUpRight()), null);
	}

	/**
	 * Inserts this node element at the specified location point in this
	 * quadtree
	 */
	public void insert(CartesianPoint point, NodeType element) {
		if (!coverage.contains(point, true))
			throw new IllegalArgumentException("Invalid insertion coordinates: " + point);
		QuadTreeNode node = new QuadTreeNode(point, element);
		root.insert(node);
		size ++;
	}

	/**
	 * Returns the maximum depth of this quadtree, where the depth of 
	 * the root node is zero.
	 */
	public int depth() {
		// TODO make less naive
		ArrayList<QuadTreeNode> list = new ArrayList<QuadTreeNode>();
		ArrayList<QuadTreeNode> nextList;
		list.add(root);
		int depth = -1;
		while(!list.isEmpty()) {
			nextList = new ArrayList<QuadTreeNode>();
			depth ++;
			for(QuadTreeNode node : list) {
				if (node.lowLeft != null)
					nextList.add(node.lowLeft);
				if (node.upLeft != null)
					nextList.add(node.upLeft);
				if (node.lowRight != null)
					nextList.add(node.lowRight);
				if (node.upRight != null)
					nextList.add(node.upRight);
			}
			list = nextList;
		}
			
		return depth;
	}

	/**
	 * Returns an iterable that contains all the elements contained
	 * in this quadtree, unordered
	 */
	public Iterable<NodeType> iterator() {
		QuadTreeNode node;
		LinkedList<NodeType> iterator;
		LinkedList<QuadTreeNode> fringe;
		iterator = new LinkedList<NodeType>();
		fringe = new LinkedList<QuadTreeNode>();
		fringe.add(root);
		while (!fringe.isEmpty()) {
			node = fringe.removeFirst();
			if (node.element != null)
				iterator.add(node.element);

			if (node.lowLeft != null)
				fringe.add(node.lowLeft);
			if (node.upLeft != null)
				fringe.add(node.upLeft);
			if (node.lowRight != null)
				fringe.add(node.lowRight);
			if (node.upRight != null)
				fringe.add(node.upRight);
		}
		return iterator;
	}

	/**
	 * Returns the closest element to the target point.  If there is
	 * a tie, chooses arbitrary closest match.  If this tree is empty,
	 * return null;
	 */
	public NodeType getClosest(CartesianPoint targetPt) {
		QuadTreeNode bestNode = null;
		ArrayList<QuadTreeNode> bucket = new ArrayList<QuadTreeNode>();
		root.convergeCollect(bucket, targetPt);
		if (bucket.size() == 0)
			return null;
		bestNode = bucket.get(0);
		for (QuadTreeNode curNode : bucket)
			if (CartesianPoint.distance(targetPt, curNode.pt) < CartesianPoint.distance(targetPt, bestNode.pt) )
				bestNode = curNode;
		return bestNode.element;
	}

	/** //TODO less naive implementation
	 * Returns the closest pair of points in this graph
	 */
	public CartesianLine getClosestPair() {
		CartesianLine closestPair;
		double minDistance, curDistance;
		closestPair = null;
		minDistance = Double.MAX_VALUE;
		for (QuadTreeNode source : nodeIterator()) {
			for (QuadTreeNode dest : nodeIterator()) {
				curDistance = CartesianPoint.distance(source.pt, dest.pt);
				if (source != dest && curDistance < minDistance) {
					minDistance = curDistance;
					closestPair = new CartesianLine(source.pt, dest.pt);
				}
			}
		}
		return closestPair;
	}
	
	public ArrayList<NodeType> getWithinBounds(RectangleArea bounds) {
		ArrayList<NodeType> bucket = new ArrayList<NodeType>();
		root.getWithinBounds(bucket, bounds, true);
		return bucket;
	}
	
	public NodeType remove(NodeType element) {
		size --;
		return null;
	}

	public int size() {
		return size;
	}

	/**
	 * Returns an iterable that contains all the nodes contained
	 * in this quadtree, unordered
	 */
	private Iterable<QuadTreeNode> nodeIterator() {
		QuadTreeNode node;
		LinkedList<QuadTreeNode> iterator;
		LinkedList<QuadTreeNode> fringe;
		iterator = new LinkedList<QuadTreeNode>();
		fringe = new LinkedList<QuadTreeNode>();
		fringe.add(root);
		while (!fringe.isEmpty()) {
			node = fringe.removeFirst();
			if (node.element != null)
				iterator.add(node);

			if (node.lowLeft != null)
				fringe.add(node.lowLeft);
			if (node.upLeft != null)
				fringe.add(node.upLeft);
			if (node.lowRight != null)
				fringe.add(node.lowRight);
			if (node.upRight != null)
				fringe.add(node.upRight);
		}
		return iterator;
	}
	
	private QuadTreeNode root;
	private int size;
	private RectangleArea coverage;



	/**
	 * The nodes to be used in this QuadTree
	 * @author Reid Hironaga
	 */
	private class QuadTreeNode {
		private QuadTreeNode( CartesianPoint aPt, NodeType aElement) {
			pt = aPt;
			element = aElement;
		}

		/**
		 * Returns the element stored at this point in the QuadTree
		 */
		private NodeType getPoint() {
			return element;
		}

		/**
		 * Finds the deepest eligible spot in the tree to insert
		 * this node, and inserts it in a vacant space
		 */
		private void insert(QuadTreeNode node) {
			CartesianPoint insertPt = node.pt;
			if (insertPt.getX() >= pt.getX()) {
				if (insertPt.getY() >= pt.getY()) {
					if(upRight == null)
						upRight = node;
					else
						upRight.insert(node);
				} else {
					if(lowRight == null)
						lowRight = node;
					else
						lowRight.insert(node);					
				}
			} else {
				if (insertPt.getY() >= pt.getY()) {
					if(upLeft == null)
						upLeft = node;
					else
						upLeft.insert(node);
				} else {
					if(lowLeft == null)
						lowLeft = node;
					else
						lowLeft.insert(node);
				}
			}
		}

		/**
		 * Converges to point from this node, collecting any potential closest
		 * euclidean distance points 
		 */
		private void convergeCollect(ArrayList<QuadTreeNode> bucket, CartesianPoint point) {
			if (element != null)
				bucket.add(this);
			// target is to the right
			if (point.getX() >= pt.getX()) {
				if (upRight != null)
					upRight.convergeCollect(bucket, point);
				if (lowRight != null)
					lowRight.convergeCollect(bucket, point);
				
				if (point.getY() >= pt.getY() && upLeft != null)
					upLeft.convergeCollect(bucket, point);
				else if (point.getY() < pt.getY() && lowLeft != null)
					lowLeft.convergeCollect(bucket, point);
			} 
			// target is to the left
			else {
				if (upLeft != null)
					upLeft.convergeCollect(bucket, point);
				if (lowLeft != null)
					lowLeft.convergeCollect(bucket, point);
				
				if (point.getY() >= pt.getY() && upRight != null)
					upRight.convergeCollect(bucket, point);
				else if (point.getY() < pt.getY() && lowRight != null)
					lowRight.convergeCollect(bucket, point);
			}
		}
		
		/**
		 * Converges to point from this node, collecting any potential closest
		 * euclidean distance points 
		 */
		private void inclusiveCollect(ArrayList<QuadTreeNode> bucket) {
			if (element != null)
				bucket.add(this);
			if (upRight != null)
				upRight.inclusiveCollect(bucket);
			if (lowRight != null)
				lowRight.inclusiveCollect(bucket);
			if (upLeft != null)
				upLeft.inclusiveCollect(bucket);
			if (lowLeft != null)
				lowLeft.inclusiveCollect(bucket);
		}
		
//		/**
//		 * Returns the closest pair of points
//		 * @return
//		 */
//		private CartesianLine closestPair() {
//			CartesianLine result;
//			if (upRight == null && lowRight == null && upLeft == null && lowLeft == null)
//				return null;
//			ArrayList<QuadTreeNode> left = new ArrayList<QuadTreeNode>();
//			ArrayList<QuadTreeNode> right = new ArrayList<QuadTreeNode>();
//			upRight.inclusiveCollect(right);
//			lowRight.inclusiveCollect(right);
//			upLeft.inclusiveCollect(left);
//			lowLeft.inclusiveCollect(left);
//			
//			
//			return result;
//		} //TODO


		private void getWithinBounds(ArrayList<NodeType> bucket, RectangleArea bounds, boolean b) {
			// TODO Auto-generated method stub
			CartesianPoint lowLeftBound, upRightBound;
			if (bounds.contains(pt, true) && element != null)
				bucket.add(element);
			
			lowLeftBound = bounds.getLowLeft();
			upRightBound = bounds.getUpRight();
			
			// bound is at least on left side (II, III)
			if (pt.getX() >= lowLeftBound.getX()) {				
				if (pt.getY() >= lowLeftBound.getY() && lowLeft != null)
					lowLeft.getWithinBounds(bucket, bounds, b); // Quadrant III
				if (pt.getY() <= upRightBound.getY() && upLeft != null)
					upLeft.getWithinBounds(bucket, bounds, b); // Quadrant II
			}

			// bound is at least on right side (I, IV)
			if (pt.getX() <= upRightBound.getX() ) {
				if (pt.getY() >= lowLeftBound.getY() && lowRight != null)
					lowRight.getWithinBounds(bucket, bounds, b); // Quadrant IV
				if (pt.getY() <= upRightBound.getY() && upRight != null)
					upRight.getWithinBounds(bucket, bounds, b); // Quadrant I
			}

		}

		private QuadTreeNode upRight;
		private QuadTreeNode lowRight;
		private QuadTreeNode upLeft;
		private QuadTreeNode lowLeft;
		private CartesianPoint pt;
		private NodeType element;
	}



	@Override
	public void insert(NodeType element) {
		// TODO Auto-generated method stub
		
	}
	
}
